package problems;

import java.util.HashSet;
import java.util.Set;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;

public class Euler082 extends Euler081 {

	@Override
	protected Set<Direction> getAllowedDirections() {
		Set<Direction> allowedDirections = new HashSet<Direction>();
		allowedDirections.add(Direction.RIGHT);
		allowedDirections.add(Direction.DOWN);
		allowedDirections.add(Direction.UP);
		return allowedDirections;
	}
	
	@Override
	protected Number calculate(int[][] inputGrid) {
		MatrixCell[][] cells = createMatrixCellArray(inputGrid);
		SimpleDirectedWeightedGraph<MatrixCell, DefaultWeightedEdge> graph = createGraph(cells, getAllowedDirections());
		
		int lowestMinimalPathSum = Integer.MAX_VALUE;
		
		//try all paths from each cell on the left column to each cell on the right column
		for (int leftRow = 0; leftRow < cells.length; leftRow++) {
			for (int rightRow = 0; rightRow < cells.length; rightRow++) {
				int minimalPathSum = minimalPathSum(graph, cells[leftRow][0], cells[rightRow][cells[0].length - 1]);
				if (minimalPathSum < lowestMinimalPathSum) {
					System.out.println("path from " + leftRow + " to " + rightRow + " is " + minimalPathSum + " which is less than " + lowestMinimalPathSum);
					lowestMinimalPathSum = minimalPathSum;
				}
			}
		}
		return lowestMinimalPathSum;
	}

	
	@Override
	protected Number getCorrectAnswer() {
		return 260324;
	}
	
	protected int getSmallGridAnswer() {
		return 994;
	}
}
